#include<stdio.h>
#include<iostream>
#include<cmath>
#include<vector>

#define maxsize 20

int Mode()//判断储存类型
{
  std::cout<<"输入储存类型："<<std::endl;
  std::cout<<"注意：邻接表输入0，邻接矩阵输入1，自动判断输入-1"<<std::endl;
  int mode;
  std::cin>>mode;
  return mode;
}

template<typename Vname>//定义点的名称类型为Vname，模板化减少复制
class Graph//定义Graph类
{
private:
  int MODE;//储存模式
  int Vnum;//点数量
  int Enum;//边数量
  bool Directed;//是否有向

  //定义边的类
  struct ENode
  {
    int start;//边起始点位置
    int end;//边结束点位置
    double weight = 1.0;//边权，默认为1
    ENode *next = nullptr;//指向下一条边的指针，默认为空
  };

  //定义点的类
  struct VNode
  {
  public:
    Vname name;
    ENode *prev = nullptr;//指向与点相连边的指针，默认为空
  };

  //用数组存储点和边
  VNode vertex[maxsize];//点数组
  ENode edge[maxsize*maxsize];//边数组
  double matrix[maxsize][maxsize] = {0};//邻接矩阵初始化

public:
  Vname getName(VNode & v)const//读入v点的名字
  {
    return v.name;
  }

  void getVertex()//读入点
  {
    std::cout<<"输入点的数量："<<std::endl;
    std::cin>>Vnum;
    std::cout<<"输入点的名称："<<std::endl;
    for(int i=0; i<Vnum; i++)
      std::cin>>vertex[i].name;
  }
  
  void getEdge()//读入边
  {
    std::cout<<"输入边的数量："<<std::endl;
    std::cin>>Enum;
    std::cout<<"输入边的前后点位置与权重："<<std::endl;
    for(int i=0; i<Enum; i++)
      std::cin>>edge[i].start>>edge[i].end>>edge[i].weight;
  }

  void getDirected()//读入图的有向性
  {
    std::cout<<"图是否有向："<<std::endl;
    std::cout<<"注意：若为有向图则输入1,若为无向图则输入0"<<std::endl;
    std::cin>>Directed;
  }
  
  void List()//生成邻接表
  {
    MODE=0;
    int j;
    if(!Directed)//若为无向图，则视其为双向补充
      {
	for(j=0; j<Enum; j++)
	  {
	    edge[j+Enum].start = edge[j].end;
	    edge[j+Enum].end = edge[j].start;
	    edge[j+Enum].weight = edge[j].weight;
	  }
      }
    for(int i=0; i<Vnum; i++)
      {
	int k;
	if(Directed) k=Enum;
	else k=Enum*2;
	for(j=0; j<k; j++)
	  {
	    if(edge[j].start == i)
	      {
		edge[j].next = vertex[i].prev;
		vertex[i].prev = & edge[j];
	      }
	  }
      }
  }

  void Matrix()//生成邻接矩阵
  {
    MODE=1;
    for(int i=0; i<Enum; i++)
      {
	 matrix[edge[i].start][edge[i].end] = edge[i].weight;
	 if(!Directed)
	   matrix[edge[i].end][edge[i].start] = edge[i].weight;
      } 
  }

  void _Graph()//生成图
  {
    int mode = Mode();
    getVertex();
    getEdge();
    getDirected();
    if(mode == 0)
      List();
    else if(mode == 1)
      Matrix();
    else if(mode == -1)
    {
      if(Enum >= Vnum*(log(Vnum)))
	Matrix();
      else
	List();
    }
    else
      std::cout<<"储存类型输入错误！"<<std::endl;
  }

  void printList()//输出邻接表
  {
    std::cout<<"邻接表:"<<std::endl;
    ENode* tmp;
    for(int i=0; i<Vnum; i++)
    {
      std::cout<<i;
      if(vertex[i].prev == nullptr)
        std::cout<<"-->null"<<std::endl;
      else
      {
	std::cout<<"-->"<<(*(vertex[i].prev)).end;
	tmp = (*(vertex[i].prev)).next;
        while(tmp != nullptr)
	{
	  std::cout<<"-->"<<(*(tmp)).end;
     	  tmp = tmp->next;
     	}
	std::cout<<"-->null"<<std::endl;
      }
    }
  }

  void printMatrix()//输出邻接矩阵
  {
    std::cout<<"邻接矩阵:"<<std::endl;
    for(int i=0; i<Vnum; i++)
    {
      for(int j=0; j<Vnum; j++)
      {
	if(i!=j && matrix[i][j]==0)
	  std::cout<<"Inf"<<"\t";
	else
	  std::cout<<matrix[i][j]<<"\t";
      }
      std::cout<<std::endl;
    }
  }

  void printGraph()//输出图
  {
    if(MODE)
      printMatrix();
    else
      printList();
  }
  
  void listVertexes()//列出所有点
  {
    std::cout<<"图中所有点："<<std::endl;
    for(int i=0; i<Vnum; i++)
      {
      std::cout<<vertex[i].name<<'\t';
      }
    std::cout<<std::endl;
  }

  void listEdges()//列出所有边
  {
    std::cout<<"图中所有边："<<std::endl;
    for(int i=0; i<Enum; i++)
    {
      std::cout<<"("<<edge[i].start<<","<<edge[i].end<<",";
      std::cout<<edge[i].weight<<")"<<std::endl;
    }
  }
};
